package 回溯;

import java.util.ArrayList;
import java.util.List;

public class _22_括号生成 {
    public List<String> generateParenthesis(int n) {
        char[] arr = new char[]{'(', ')'};
        List<String> res = new ArrayList<>();
        List<Character> temp = new ArrayList<>();
        backtrack(res, temp, arr, n * 2, 0, 0, 0, 0);
        return res;
    }

    private void backtrack(List<String> res, List<Character> temp, char[] arr, int len, int level, int begin, int left, int right) {
        if (level == len) {
            char[] carr = new char[temp.size()];
            for (int i = 0; i < carr.length; i++) {
                carr[i] = temp.get(i);
            }
            res.add(new String(carr));
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == '(' && left < (len >> 1)) {
                temp.add(arr[i]);
                backtrack(res, temp, arr, len, level + 1, i + 1, left + 1, right);
                temp.remove(temp.size() - 1);
            }
            if (arr[i] == ')' && left > right) {
                temp.add(arr[i]);
                backtrack(res, temp, arr, len, level + 1, i + 1, left, right + 1);
                temp.remove(temp.size() - 1);
            }
        }
    }


}
